package com.jack.leetcode.eachproblem_2020;

import java.util.Stack;

public class 拼接最大数 {

    public static void main(String[] args) {
//        int[] a = {3, 4, 6, 5};
//        int[] b = {9, 1, 2, 5, 8, 3};
//        maxNumber(a, b, 5);

        int[] c = {2,5,6,4,4,0};
        int[] d = {7,3,8,0,6,5,7,6,2};
        maxNumber(c, d, 15);
    }

    public static int[] maxNumber(int[] nums1, int[] nums2, int k) {
        int[] result = new int[k];
        String tmp = "";
        for(int i = 0;i < k + 1;i++){
            if(i <= nums1.length && k - i <= nums2.length){
                String mergeResult = merge(picMax(nums1, nums1.length - i),
                        picMax(nums2, nums2.length- k + i));
                tmp = tmp.compareTo(mergeResult) < 0 ? mergeResult : tmp;
            }
        }
        int index = 0;
        for(char c : tmp.toCharArray()){
            result[index++] = c - '0';
        }
        return result;
    }

    private static String merge(String a, String b){
        StringBuilder result = new StringBuilder();
        int cur = 0, p1 = 0, p2 = 0;
        while(cur < a.length() + b.length()){
            if(compare(a, p1, b, p2)){
                result.append(a.charAt(p1++));
                cur++;
            }else{
                result.append(b.charAt(p2++));
                cur++;
            }
        }
        return result.toString();
    }

    public static boolean compare(String nums1, int p1, String nums2, int p2) {
        if (p2 >= nums2.length()) return true;
        if (p1 >= nums1.length()) return false;
        if (nums1.charAt(p1) > nums2.charAt(p2)) return true;
        if (nums1.charAt(p1) < nums2.charAt(p2)) return false;
        return compare(nums1, p1 + 1, nums2, p2 + 1);
    }

    private static String picMax(int[] nums, int i){
        int n = nums.length;
        if(n == i){
            return "";
        }
        int newLength = n - i;
        StringBuilder result = new StringBuilder();
        Stack<Integer> stack = new Stack<>();
        for(int c : nums){
            while(i != 0 && !stack.isEmpty() && stack.peek() < c){
                stack.pop();
                i -= 1;
            }
            stack.add(c);
        }
        while(!stack.isEmpty() && stack.firstElement() == '0'){
            stack.remove(0);
        }
        if(stack.isEmpty()){
            return "";
        }
        stack.stream().limit(newLength).forEach(s -> result.append(s));
        return result.toString();
    }
}
